/*
 * heap_sort.c
 *
 *  Created on: Mar 25, 2014
 *      Author: jack
 */
#include<stdio.h>

void heap_sort(int arr[],int len) {
	int i,j;
	//构建堆
	for(i=len/2;i>=0;i--){
		heap_adjust(arr,i,len-1);
	}
	//执行排序
	for(i=len-1;i>=0;i--) {
		int tmp = arr[0];
		arr[0]=arr[i];
		arr[i] = tmp;
		heap_adjust(arr,0,i-1);
	}
}

void heap_adjust(int arr[],int s,int m) {
	int key = arr[s];
	int i;
	for(i=2*s;i<=m;i=i*2) {
		if(i+1<=m && arr[i]<arr[i+1]) i++;
		if(key < arr[i]) {
			arr[s] = arr[i];
			s = i;
		}else {
			break;
		}
	}
	arr[s]=key;
}

